/**
 * Method 2: using dynamic programming, which will not work if n is large.
 * it will exceed the memory limit.
 */

/**
 * @author antonio081014
 * @since Dec 23, 2011, 6:07:14 PM
 */

public class MagicCandy {

	public int whichOne(int n) {
		int step = 0;
		while (n > 1) {
			step++;
			n -= (int) Math.sqrt(n);
		}
		int e = 1;
		for (int i = 0; i < step; i++)
			e += (int) Math.sqrt(e + Math.sqrt(e));
		return e;
	}

	public int[] map;
	public int[] counts;

	public int whichOne2(int n) {

		map = new int[n + 1];
		counts = new int[n + 1];
		int count = 0;
		for (int i = 1; i <= n; i++) {
			if (isMagic(i)) {
				count++;
				counts[i] = 1;
			}
			map[i] = count;
		}
		int ret = -1;
		int mmax = 0;
		for (int i = 1; i <= n; i++) {
			if (getDepth(i) > mmax) {
				mmax = counts[i];
				ret = i;
			}
		}
		return ret;
	}

	public int getDepth(int n) {
		if (counts[n] != 0)
			return counts[n];
		counts[n] = 1 + getDepth(n - map[n]);
		return counts[n];
	}

	public boolean isMagic(int n) {
		int x = (int) Math.sqrt(n);
		if (n == x * x)
			return true;
		return false;
	}

	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
